import random
import sys
import parse
import time
import os
import copy
from collections import deque


def expectimax_single_ghost(problem, k, verbose):
    # Your p5 code here
    seed = problem['seed']
    if seed != -1:
        random.seed(seed, version=1)
    round = 0
    score = 0
    solution = 'seed: ' + str(seed) + '\n'
    winner = 'Ghost'
    queue = deque(['P'] + problem['ghostList'])
    agentDict = {'P': 0,
                 'W': 1,
                 'X': 2,
                 'Y': 3,
                 'Z': 4,
                 0: 'P',
                 1: 'W',
                 2: 'X',
                 3: 'Y',
                 4: 'Z'}

    while len(problem['pacmanLoc']) > 0 and len(problem['foodLoc']) > 0:
        if round == 0:
            solution = pack_solution(solution, round, problem['map'], '', '', '',
                                     problem['pacmanLoc'], problem['ghostLoc'], problem['foodLoc'])
        else:
            tempFoodLoc = copy.deepcopy(problem['foodLoc'])
            tempPacmanLoc = copy.deepcopy(problem['pacmanLoc'])
            tempGhostLoc = copy.deepcopy(problem['ghostLoc'])
            ch = queue.popleft()
            queue.append(ch)
            dir = min_max(agentDict[ch], agentDict[ch], problem['map'], 0, k, len(queue),
                          tempFoodLoc, tempPacmanLoc, tempGhostLoc, 0, agentDict)
            choose, score = move(
                ch, problem['pacmanLoc'], problem['ghostLoc'], problem['foodLoc'], score, dir)
            solution = pack_solution(solution, round, problem['map'], ch, choose, score,
                                     problem['pacmanLoc'], problem['ghostLoc'], problem['foodLoc'])
        round += 1

    if len(problem['foodLoc']) == 0:
        winner = 'Pacman'

    solution += f"WIN: {winner}"

    return solution, winner


def pack_solution(solution, round, map, ch, dir, score, pacmanLoc, ghostLoc, foodLoc):
    tempMap = map
    if round == 0:
        solution += f"{round}\n"
    elif dir == '':
        solution += f"{round}: {ch} moving \n"
    else:
        solution += f"{round}: {ch} moving {dir}\n"

    if len(pacmanLoc) > 0:
        tempMap[pacmanLoc[0]][pacmanLoc[1]] = 'P'

    if len(foodLoc) > 0:
        for food in foodLoc.keys():
            tempMap[food[0]][food[1]] = '.'

    if len(ghostLoc) > 0:
        for key in ghostLoc.keys():
            tempMap[ghostLoc[key][0]][ghostLoc[key][1]] = key

    for row in tempMap:
        solution += ''.join(row) + '\n'

    solution += f"score: {score}\n" if round != 0 else ""
    return solution


def get_score(isLose, isWin, score):
    if isLose:
        score -= 500
    elif isWin:
        score += 500

    return score


def move_get_score(agent, newLoc, foodLoc, pacmanLoc, ghostLoc, score):
    if agent == 'P':
        if newLoc in ghostLoc.values():
            pacmanLoc.clear()
            score -= 1
        elif (newLoc[0], newLoc[1]) in foodLoc.keys():
            score += 9
            del foodLoc[(newLoc[0], newLoc[1])]
            pacmanLoc[0] = newLoc[0]
            pacmanLoc[1] = newLoc[1]
        else:
            pacmanLoc[0] = newLoc[0]
            pacmanLoc[1] = newLoc[1]
            score -= 1
    else:
        if newLoc[0] == pacmanLoc[0] and newLoc[1] == pacmanLoc[1]:
            pacmanLoc.clear()
        ghostLoc[agent] = [newLoc[0], newLoc[1]]

    return score


def isLose(pacmanLoc):
    return len(pacmanLoc) == 0


def isWin(foodLoc):
    return len(foodLoc) == 0


def move(ch, pacmanLoc, ghostLoc, foodLoc, score, choose):
    if choose == '':
        return choose, score

    location = pacmanLoc if ch == 'P' else ghostLoc[ch]

    if choose == 'N':
        newLoc = [location[0] - 1, location[1]]
    elif choose == 'E':
        newLoc = [location[0], location[1] + 1]
    elif choose == 'S':
        newLoc = [location[0] + 1, location[1]]
    else:
        newLoc = [location[0], location[1] - 1]

    if ch == 'P':
        if [newLoc[0], newLoc[1]] in ghostLoc.values():
            pacmanLoc.clear()
            score -= 501
        elif (newLoc[0], newLoc[1]) in foodLoc.keys():
            score += 9
            del foodLoc[(newLoc[0], newLoc[1])]
            pacmanLoc[0] = newLoc[0]
            pacmanLoc[1] = newLoc[1]
            if len(foodLoc) == 0:
                score += 500
        else:
            pacmanLoc[0] = newLoc[0]
            pacmanLoc[1] = newLoc[1]
            score -= 1
    else:
        if newLoc[0] == pacmanLoc[0] and newLoc[1] == pacmanLoc[1]:
            pacmanLoc.clear()
            score -= 500
        ghostLoc[ch] = [newLoc[0], newLoc[1]]

    return choose, score


def get_new_directions(ch, map, location, ghostLoc):
    newLocDir = {}

    if ch == 'P':
        # check east
        if map[location[0]][location[1] + 1] != '%':
            newLocDir['E'] = [location[0], location[1] + 1]
        # check north
        if map[location[0] - 1][location[1]] != '%':
            newLocDir['N'] = [location[0] - 1, location[1]]
        # check south
        if map[location[0] + 1][location[1]] != '%':
            newLocDir['S'] = [location[0] + 1, location[1]]
        # check west
        if map[location[0]][location[1] - 1] != '%':
            newLocDir['W'] = [location[0], location[1] - 1]
    else:
        # check east
        if map[location[0]][location[1]+1] != '%' and \
                [location[0], location[1] + 1] not in ghostLoc.values():
            newLocDir['E'] = [location[0], location[1] + 1]
        # check north
        if map[location[0]-1][location[1]] != '%' and \
                [location[0] - 1, location[1]] not in ghostLoc.values():
            newLocDir['N'] = [location[0] - 1, location[1]]
        # check south
        if map[location[0]+1][location[1]] != '%' and \
                [location[0] + 1, location[1]] not in ghostLoc.values():
            newLocDir['S'] = [location[0] + 1, location[1]]
        # check west
        if map[location[0]][location[1]-1] != '%' and \
                [location[0], location[1] - 1] not in ghostLoc.values():
            newLocDir['W'] = [location[0], location[1] - 1]

    return newLocDir


def min_max(initAgent, agent, map, depth, maxDepth, maxAgent, foodLoc, pacmanLoc, ghostLoc, score, agentDict):
    if isLose(pacmanLoc) or isWin(foodLoc) or depth == maxDepth:
        return get_score(isLose(pacmanLoc), isWin(foodLoc), score)

    newLoc = pacmanLoc if agent == 0 else ghostLoc[agentDict[agent]]
    availableDirs = get_new_directions(agentDict[agent], map, newLoc, ghostLoc)
    values = list(availableDirs.values())
    if len(values) == 0 and depth == 0 and initAgent == agent:
        return ''

    if agent == 0:
        maxValList = []
        for newLocation in values:
            tempFoodLoc = copy.deepcopy(foodLoc)
            tempPacmanLoc = copy.deepcopy(pacmanLoc)
            tempGhostLoc = copy.deepcopy(ghostLoc)
            tempScore = move_get_score(
                agentDict[agent], newLocation, tempFoodLoc, tempPacmanLoc, tempGhostLoc, score)
            maxValList.append(min_max(initAgent, 1, map, depth, maxDepth, maxAgent, tempFoodLoc,
                                      tempPacmanLoc, tempGhostLoc, tempScore, agentDict))
        maxVal = max(maxValList)
        if initAgent == agent and depth == 0:
            indexes = [i for i, x in enumerate(maxValList) if x == maxVal]
            keys = list(availableDirs.keys())
            index = random.choice(tuple(indexes))
            return keys[index]
        return maxVal
    else:
        nextAgent = agent + 1
        if nextAgent == maxAgent:
            nextAgent = 0
        if nextAgent == 0:
            tempDepth = depth + 1
        else:
            tempDepth = depth
        minValList = []
        if len(values) == 0:
            tempFoodLoc = copy.deepcopy(foodLoc)
            tempPacmanLoc = copy.deepcopy(pacmanLoc)
            tempGhostLoc = copy.deepcopy(ghostLoc)
            minValList.append(min_max(initAgent, nextAgent, map, tempDepth, maxDepth, maxAgent, tempFoodLoc,
                                      tempPacmanLoc, tempGhostLoc, score, agentDict))
        else:
            for newLocation in values:
                tempFoodLoc = copy.deepcopy(foodLoc)
                tempPacmanLoc = copy.deepcopy(pacmanLoc)
                tempGhostLoc = copy.deepcopy(ghostLoc)
                tempScore = move_get_score(
                    agentDict[agent], newLocation, tempFoodLoc, tempPacmanLoc, tempGhostLoc, score)
                minValList.append(min_max(initAgent, nextAgent, map, tempDepth, maxDepth, maxAgent, tempFoodLoc,
                                          tempPacmanLoc, tempGhostLoc, tempScore, agentDict))

        minVal = min(minValList)
        if initAgent == agent and depth == 0:
            indexes = [i for i, x in enumerate(minValList) if x == minVal]
            keys = list(availableDirs.keys())
            index = random.choice(tuple(indexes))
            return keys[index]
        return minVal


if __name__ == "__main__":
    test_case_id = int(sys.argv[1])
    problem_id = 5
    file_name_problem = str(test_case_id)+'.prob'
    file_name_sol = str(test_case_id)+'.sol'
    path = os.path.join('test_cases', 'p'+str(problem_id))
    problem = parse.read_layout_problem(os.path.join(path, file_name_problem))
    k = int(sys.argv[2])
    num_trials = int(sys.argv[3])
    verbose = bool(int(sys.argv[4]))
    print('test_case_id:', test_case_id)
    print('k:', k)
    print('num_trials:', num_trials)
    print('verbose:', verbose)
    start = time.time()
    win_count = 0
    for i in range(num_trials):
        solution, winner = expectimax_single_ghost(
            copy.deepcopy(problem), k, verbose)
        if winner == 'Pacman':
            win_count += 1
        if verbose:
            print(solution)
    win_p = win_count/num_trials * 100
    end = time.time()
    print('time: ', end - start)
    print('win %', win_p)
